1. Field of the Invention
This invention relates to reordering data units for reading and writing memory, such as for example used in packet buffering in a packet router.
In a computer network, routing devices receive messages at one of a set of input interfaces, and forward them on to one of a set of output interfaces. It is advantageous for such routing devices to operate as quickly as possible so as to keep up with the rate of incoming messages. As they are received at an input interface, packets are read from the input interface into a memory, a decision is made by the router regarding to which output interface the packet is to be sent, and the packet is read from the memory to the output interface.
One problem in the known art is that packets are often of differing lengths, so that storing the packet in memory can use multiple cells of that memory. This complicates the decision of where in the memory to record the packet, and, depending on the nature of the memory, can slow the operations of reading packets into memory or reading packets from memory.
This problem in the known art is exacerbated by the relative speed with which memory can read and write. As memory becomes ever faster, the desirability of using the relative speed of that memory becomes ever greater. This problem is particularly acute when the memory itself has a plurality of memory banks capable of operating concurrently. Moreover, this problem is exacerbated when memory transfers use a relatively wide data transfer width; transfers that require just one or a few bytes more than the maximum transfer width waste relatively more memory read and write bandwidth as the data transfer width becomes relatively larger.
Accordingly, it would be advantageous to provide a packet buffer memory that uses as much of the speed of the memory as possible, particularly when that memory has banks which are capable of operating concurrently. This advantage is achieved in an embodiment of the invention in which packets are divided into cells, cells are allocated to memory banks capable of operating concurrently, and packets are reconstructed from the cells that were recorded in memory. Writing cells into the memory and reading cells from the memory need not occur in the same order in which those cells are received.
The invention is directed to a method and system for reordering data units that are to be written to, or read from, selected locations in a memory. The data units are re-ordered so that an order of accessing memory (or portions thereof) is optimal for speed of reading or writing memory, not necessarily an order in which data units were received or requested.
The invention is applicable to a packet memory, and a method for operating that packet memory, so as to use as much memory speed as possible. Packets that are received at input interfaces are divided into cells, with the cells being allocated to independent memory banks. Many such memory banks are kept busy concurrently, so the cells (and thus the packets) are read into the memory as rapidly as possible. A set of first-in-first-out (FIFO) queues includes one queue for each such memory bank, and is disposed in a sequence of rows (herein called xe2x80x9cstripesxe2x80x9d) so as to have one queue element for each time slot to write to the memory. The FIFO queues can include cells in each stripe from more than one complete packet, so as to reduce the number of memory operations for multiple packets.
In a preferred embodiment, as packets are received, their packet information is disassembled into cells of a uniform size. The individual cells are mapped to sequential memory addresses, in response to the order in which they appear in packets, and in response to the packet queue(s) the packet is to be written to. When the memory is ready to read cells into the memory, a stripe of cells from those queues is read into the memory.
Similarly, for packets that are to be sent to output interfaces, cells can be located in the independent memory banks and read therefrom, so the cells (and thus the packets) are read out of the memory as rapidly as possible. Cells from the memory can be placed in individual queues for each memory bank. When the memory is ready to read cells out of the memory, one stripe of cells from those queues can be read out of the memory, and packets can be reassembled from those cells.
In a preferred embodiment, each stripe of cells to be read into or read out of the memory is filled, as much as possible, before the next memory cycle, so as to make most efficient use of the parallel capacity of the memory. Similarly, stripes of cells to be read into or read out of the memory are also filled, as much as possible, in advance, so that memory cycles can be performed rapidly without waiting for filling any individual memory bank queue. Either of these might involve advancing cells of one or more packets out of order from the rest of their packet, so as to maintain one or more memory banks busy.